package test2;

import java.util.Arrays;

public class demo51 {
    class Solution {
        public int minFallingPathSum(int[][] matrix) {
            int n = matrix.length;
            int[][] dp = new int[n][n];
            System.arraycopy(matrix[0], 0, dp[0], 0, n);
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int mn = dp[i - 1][j];
                    if (j > 0) {
                        mn = Math.min(mn, dp[i - 1][j - 1]);
                    }
                    if (j < n - 1) {
                        mn = Math.min(mn, dp[i - 1][j + 1]);
                    }
                    dp[i][j] = mn + matrix[i][j];
                }
            }
            return Arrays.stream(dp[n - 1]).min().getAsInt();
        }
    }

}
